'''
https://leetcode.cn/problems/network-delay-time/description/
'''
import heapq
from collections import defaultdict
from typing import List


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        distance = [float('inf')] * (n + 1)
        distance[k] = 0
        visited = [False] * (n + 1)

        heap = [(0, k)]
        while heap:
            cost, u = heapq.heappop(heap)
            if not visited[u]:
                visited[u] = True
                for v, w in graph[u]:
                    if not visited[v] and cost + w < distance[v]:
                        distance[v] = cost + w
                        heapq.heappush(heap, (distance[v], v))
        ans = max(distance[1:])
        return -1 if ans == float('inf') else ans
